package pyip.lib.javalearn.algorithm.sort;


/**
 * 希尔排序（最小增量排序）<br>
 * 基本思想：算法先将要排序的一组数按某个增量d（n/2,n为要排序数的个数）分成若干组，每组中记录的下标相差d。<br>
 * 对每组中全部元素进行直接插入排序，然后再用一个较小的增量（d/2）对它进行分组，在每组中再进行直接插入排序。当增量减到1时，进行直接插入排序后，排序完成。
 * @author yepeng
 * @date 2015年9月2日
 */
public class ShellSort implements Sort {

    @Override
    public void sort(int[] arr, boolean asc) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        double d1 = arr.length;
        int temp = 0;
        while (true) {
            d1 = Math.ceil(d1 / 2);
            int d = (int) d1;
            for (int x = 0; x < d; x++) {
                for (int i = x + d; i < arr.length; i += d) {
                    int j = i - d;
                    temp = arr[i];
                    for (; j >= 0 && temp < arr[j]; j -= d) {
                        arr[j + d] = arr[j];
                    }
                    arr[j + d] = temp;
                }
            }
            if (d == 1)
                break;
        }

    }

}
